/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / src / c / modtrees.nw

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 20 43 6f 70 79 72 69 | 67 68 74 20 31 39 39 31 |% Copyri|ght 1991|
|00000010| 20 62 79 20 4e 6f 72 6d | 61 6e 20 52 61 6d 73 65 | by Norm|an Ramse|
|00000020| 79 2e 20 20 41 6c 6c 20 | 72 69 67 68 74 73 20 72 |y.  All |rights r|
|00000030| 65 73 65 72 76 65 64 2e | 0d 25 20 53 65 65 20 66 |eserved.|.% See f|
|00000040| 69 6c 65 20 43 4f 50 59 | 52 49 47 48 54 20 66 6f |ile COPY|RIGHT fo|
|00000050| 72 20 6d 6f 72 65 20 69 | 6e 66 6f 72 6d 61 74 69 |r more i|nformati|
|00000060| 6f 6e 2e 0d 40 20 0d 5c | 73 75 62 73 65 63 74 69 |on..@ .\|subsecti|
|00000070| 6f 6e 7b 53 75 70 70 6f | 72 74 20 66 6f 72 20 6c |on{Suppo|rt for l|
|00000080| 6f 6f 6b 69 6e 67 20 75 | 70 20 6d 6f 64 75 6c 65 |ooking u|p module|
|00000090| 73 20 62 79 20 6e 61 6d | 65 7d 0d 54 72 65 65 73 |s by nam|e}.Trees|
|000000a0| 20 6f 66 20 6d 6f 64 75 | 6c 65 73 2e 0d 41 20 74 | of modu|les..A t|
|000000b0| 61 62 6c 65 20 6f 66 20 | 6d 6f 64 75 6c 65 73 20 |able of |modules |
|000000c0| 77 69 74 68 20 69 6e 73 | 65 72 74 20 61 6e 64 20 |with ins|ert and |
|000000d0| 6c 6f 6f 6b 75 70 2c 20 | 62 75 74 20 6e 6f 20 64 |lookup, |but no d|
|000000e0| 65 6c 65 74 65 2e 0d 54 | 68 65 20 6b 65 79 20 69 |elete..T|he key i|
|000000f0| 73 20 74 68 65 20 6d 6f | 64 75 6c 65 20 6e 61 6d |s the mo|dule nam|
|00000100| 65 2e 0d 3c 3c 68 65 61 | 64 65 72 3e 3e 3d 0d 4d |e..<<hea|der>>=.M|
|00000110| 6f 64 75 6c 65 20 69 6e | 73 65 72 74 20 28 63 68 |odule in|sert (ch|
|00000120| 61 72 20 2a 6d 6f 64 6e | 61 6d 65 29 3b 20 20 2f |ar *modn|ame);  /|
|00000130| 2a 20 61 64 64 20 61 20 | 6d 6f 64 75 6c 65 20 74 |* add a |module t|
|00000140| 6f 20 74 68 65 20 77 6f | 72 6c 64 20 2a 2f 0d 4d |o the wo|rld */.M|
|00000150| 6f 64 75 6c 65 20 6c 6f | 6f 6b 75 70 20 28 63 68 |odule lo|okup (ch|
|00000160| 61 72 20 2a 6d 6f 64 6e | 61 6d 65 29 3b 20 20 2f |ar *modn|ame);  /|
|00000170| 2a 20 72 65 74 75 72 6e | 20 70 74 72 20 74 6f 20 |* return| ptr to |
|00000180| 6d 6f 64 75 6c 65 20 6f | 72 20 4e 55 4c 4c 20 2a |module o|r NULL *|
|00000190| 2f 0d 76 6f 69 64 20 61 | 70 70 6c 79 5f 65 61 63 |/.void a|pply_eac|
|000001a0| 68 5f 6d 6f 64 75 6c 65 | 28 76 6f 69 64 20 28 2a |h_module|(void (*|
|000001b0| 66 75 6e 29 28 4d 6f 64 | 75 6c 65 29 29 3b 0d 20 |fun)(Mod|ule));. |
|000001c0| 20 20 20 20 2f 2a 20 61 | 70 70 6c 79 20 5b 5b 66 |    /* a|pply [[f|
|000001d0| 75 6e 5d 5d 20 74 6f 20 | 65 61 63 68 20 6d 6f 64 |un]] to |each mod|
|000001e0| 75 6c 65 20 69 6e 20 74 | 68 65 20 74 72 65 65 20 |ule in t|he tree |
|000001f0| 2a 2f 0d 3c 3c 2a 3e 3e | 3d 20 0d 23 69 6e 63 6c |*/.<<*>>|= .#incl|
|00000200| 75 64 65 20 3c 73 74 64 | 69 6f 2e 68 3e 0d 23 69 |ude <std|io.h>.#i|
|00000210| 6e 63 6c 75 64 65 20 3c | 73 74 72 69 6e 67 2e 68 |nclude <|string.h|
|00000220| 3e 0d 23 69 6e 63 6c 75 | 64 65 20 3c 73 74 64 6c |>.#inclu|de <stdl|
|00000230| 69 62 2e 68 3e 0d 23 69 | 6e 63 6c 75 64 65 20 22 |ib.h>.#i|nclude "|
|00000240| 73 74 72 73 61 76 65 2e | 68 22 0d 23 69 6e 63 6c |strsave.|h".#incl|
|00000250| 75 64 65 20 22 6d 6f 64 | 75 6c 65 73 2e 68 22 0d |ude "mod|ules.h".|
|00000260| 23 69 6e 63 6c 75 64 65 | 20 22 6d 6f 64 74 72 65 |#include| "modtre|
|00000270| 65 73 2e 68 22 0d 23 69 | 6e 63 6c 75 64 65 20 22 |es.h".#i|nclude "|
|00000280| 65 72 72 6f 72 73 2e 68 | 22 0d 0d 74 79 70 65 64 |errors.h|"..typed|
|00000290| 65 66 20 73 74 72 75 63 | 74 20 74 6e 6f 64 65 20 |ef struc|t tnode |
|000002a0| 7b 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 74 72 |{       |   /* tr|
|000002b0| 65 65 20 6e 6f 64 65 20 | 2a 2f 0d 20 20 73 74 72 |ee node |*/.  str|
|000002c0| 75 63 74 20 74 6e 6f 64 | 65 20 2a 6c 65 66 74 2c |uct tnod|e *left,|
|000002d0| 20 2a 72 69 67 68 74 3b | 0d 20 20 4d 6f 64 75 6c | *right;|.  Modul|
|000002e0| 65 20 64 61 74 61 3b 0d | 7d 20 54 4e 4f 44 45 3b |e data;.|} TNODE;|
|000002f0| 0d 0d 73 74 61 74 69 63 | 20 73 74 72 75 63 74 20 |..static| struct |
|00000300| 74 6e 6f 64 65 20 2a 72 | 6f 6f 74 3d 4e 55 4c 4c |tnode *r|oot=NULL|
|00000310| 3b 0d 20 20 20 20 20 20 | 20 20 0d 3c 3c 46 75 6e |;.      |  .<<Fun|
|00000320| 63 74 69 6f 6e 20 64 65 | 63 6c 61 72 61 74 69 6f |ction de|claratio|
|00000330| 6e 73 3e 3e 0d 3c 3c 2a | 3e 3e 3d 20 0d 4d 6f 64 |ns>>.<<*|>>= .Mod|
|00000340| 75 6c 65 20 69 6e 73 65 | 72 74 20 28 63 68 61 72 |ule inse|rt (char|
|00000350| 20 2a 6d 6f 64 6e 61 6d | 65 29 20 7b 0d 20 20 20 | *modnam|e) {.   |
|00000360| 20 72 65 74 75 72 6e 20 | 69 6e 73 65 72 74 5f 74 | return |insert_t|
|00000370| 72 65 65 20 28 26 72 6f | 6f 74 2c 20 6d 6f 64 6e |ree (&ro|ot, modn|
|00000380| 61 6d 65 29 3b 0d 7d 0d | 0d 73 74 61 74 69 63 20 |ame);.}.|.static |
|00000390| 4d 6f 64 75 6c 65 0d 69 | 6e 73 65 72 74 5f 74 72 |Module.i|nsert_tr|
|000003a0| 65 65 28 54 4e 4f 44 45 | 20 2a 2a 72 6f 6f 74 70 |ee(TNODE| **rootp|
|000003b0| 74 72 2c 20 63 68 61 72 | 20 2a 6d 6f 64 6e 61 6d |tr, char| *modnam|
|000003c0| 65 29 20 7b 0d 20 20 20 | 20 20 69 66 20 28 2a 72 |e) {.   |  if (*r|
|000003d0| 6f 6f 74 70 74 72 3d 3d | 4e 55 4c 4c 29 20 7b 0d |ootptr==|NULL) {.|
|000003e0| 20 20 20 20 20 20 20 20 | 20 3c 3c 41 6c 6c 6f 63 |        | <<Alloc|
|000003f0| 61 74 65 20 6e 65 77 20 | 74 6e 6f 64 65 20 69 6e |ate new |tnode in|
|00000400| 20 2a 2a 72 6f 6f 74 70 | 74 72 3e 3e 0d 20 20 20 | **rootp|tr>>.   |
|00000410| 20 20 20 20 20 20 72 65 | 74 75 72 6e 20 28 2a 72 |      re|turn (*r|
|00000420| 6f 6f 74 70 74 72 29 2d | 3e 64 61 74 61 20 3d 20 |ootptr)-|>data = |
|00000430| 6e 65 77 6d 6f 64 75 6c | 65 28 6d 6f 64 6e 61 6d |newmodul|e(modnam|
|00000440| 65 29 3b 0d 20 20 20 20 | 20 7d 20 0d 20 20 20 20 |e);.    | } .    |
|00000450| 20 69 66 20 28 73 74 72 | 63 6d 70 28 28 2a 72 6f | if (str|cmp((*ro|
|00000460| 6f 74 70 74 72 29 2d 3e | 64 61 74 61 2d 3e 6e 61 |otptr)->|data->na|
|00000470| 6d 65 2c 6d 6f 64 6e 61 | 6d 65 29 3d 3d 30 29 20 |me,modna|me)==0) |
|00000480| 7b 0d 20 20 20 20 20 20 | 20 20 20 72 65 74 75 72 |{.      |   retur|
|00000490| 6e 20 28 2a 72 6f 6f 74 | 70 74 72 29 2d 3e 64 61 |n (*root|ptr)->da|
|000004a0| 74 61 3b 0d 20 20 20 20 | 20 7d 20 65 6c 73 65 20 |ta;.    | } else |
|000004b0| 69 66 20 28 73 74 72 63 | 6d 70 28 28 2a 72 6f 6f |if (strc|mp((*roo|
|000004c0| 74 70 74 72 29 2d 3e 64 | 61 74 61 2d 3e 6e 61 6d |tptr)->d|ata->nam|
|000004d0| 65 2c 6d 6f 64 6e 61 6d | 65 29 3c 30 29 20 7b 0d |e,modnam|e)<0) {.|
|000004e0| 20 20 20 20 20 20 20 20 | 20 72 65 74 75 72 6e 20 |        | return |
|000004f0| 69 6e 73 65 72 74 5f 74 | 72 65 65 28 26 28 28 2a |insert_t|ree(&((*|
|00000500| 72 6f 6f 74 70 74 72 29 | 2d 3e 6c 65 66 74 29 2c |rootptr)|->left),|
|00000510| 6d 6f 64 6e 61 6d 65 29 | 3b 0d 20 20 20 20 20 7d |modname)|;.     }|
|00000520| 20 65 6c 73 65 20 2f 2a | 20 3e 30 20 2a 2f 20 7b | else /*| >0 */ {|
|00000530| 0d 20 20 20 20 20 20 20 | 20 20 72 65 74 75 72 6e |.       |  return|
|00000540| 20 69 6e 73 65 72 74 5f | 74 72 65 65 28 26 28 28 | insert_|tree(&((|
|00000550| 2a 72 6f 6f 74 70 74 72 | 29 2d 3e 72 69 67 68 74 |*rootptr|)->right|
|00000560| 29 2c 6d 6f 64 6e 61 6d | 65 29 3b 0d 20 20 20 20 |),modnam|e);.    |
|00000570| 20 7d 0d 0d 7d 0d 40 20 | 25 64 65 66 20 69 6e 73 | }..}.@ |%def ins|
|00000580| 65 72 74 0d 0d 4e 6f 64 | 65 20 61 6c 6c 6f 63 61 |ert..Nod|e alloca|
|00000590| 74 69 6f 6e 20 69 73 20 | 70 65 72 66 65 63 74 6c |tion is |perfectl|
|000005a0| 79 20 73 74 61 6e 64 61 | 72 64 2e 0d 3c 3c 41 6c |y standa|rd..<<Al|
|000005b0| 6c 6f 63 61 74 65 20 6e | 65 77 20 74 6e 6f 64 65 |locate n|ew tnode|
|000005c0| 20 69 6e 20 2a 2a 72 6f | 6f 74 70 74 72 3e 3e 3d | in **ro|otptr>>=|
|000005d0| 0d 20 20 20 20 20 20 20 | 63 68 65 63 6b 70 74 72 |.       |checkptr|
|000005e0| 28 2a 72 6f 6f 74 70 74 | 72 3d 28 73 74 72 75 63 |(*rootpt|r=(struc|
|000005f0| 74 20 74 6e 6f 64 65 20 | 2a 29 20 6d 61 6c 6c 6f |t tnode |*) mallo|
|00000600| 63 20 28 73 69 7a 65 6f | 66 28 73 74 72 75 63 74 |c (sizeo|f(struct|
|00000610| 20 74 6e 6f 64 65 29 29 | 29 3b 0d 20 20 20 20 20 | tnode))|);.     |
|00000620| 20 20 28 2a 72 6f 6f 74 | 70 74 72 29 2d 3e 6c 65 |  (*root|ptr)->le|
|00000630| 66 74 20 3d 20 28 2a 72 | 6f 6f 74 70 74 72 29 2d |ft = (*r|ootptr)-|
|00000640| 3e 72 69 67 68 74 20 3d | 20 4e 55 4c 4c 3b 0d 40 |>right =| NULL;.@|
|00000650| 0d 3c 3c 46 75 6e 63 74 | 69 6f 6e 20 64 65 63 6c |.<<Funct|ion decl|
|00000660| 61 72 61 74 69 6f 6e 73 | 3e 3e 3d 0d 73 74 61 74 |arations|>>=.stat|
|00000670| 69 63 20 4d 6f 64 75 6c | 65 20 69 6e 73 65 72 74 |ic Modul|e insert|
|00000680| 5f 74 72 65 65 28 54 4e | 4f 44 45 20 2a 2a 72 6f |_tree(TN|ODE **ro|
|00000690| 6f 74 70 74 72 2c 20 63 | 68 61 72 20 2a 6d 6f 64 |otptr, c|har *mod|
|000006a0| 6e 61 6d 65 29 3b 0d 73 | 74 61 74 69 63 20 4d 6f |name);.s|tatic Mo|
|000006b0| 64 75 6c 65 20 6c 6f 6f | 6b 75 70 5f 74 72 65 65 |dule loo|kup_tree|
|000006c0| 28 54 4e 4f 44 45 20 2a | 2a 72 6f 6f 74 70 74 72 |(TNODE *|*rootptr|
|000006d0| 2c 20 63 68 61 72 20 2a | 6d 6f 64 6e 61 6d 65 29 |, char *|modname)|
|000006e0| 3b 0d 40 0d 3c 3c 2a 3e | 3e 3d 0d 4d 6f 64 75 6c |;.@.<<*>|>=.Modul|
|000006f0| 65 20 6c 6f 6f 6b 75 70 | 20 28 63 68 61 72 20 2a |e lookup| (char *|
|00000700| 6d 6f 64 6e 61 6d 65 29 | 20 7b 0d 20 20 20 20 72 |modname)| {.    r|
|00000710| 65 74 75 72 6e 20 6c 6f | 6f 6b 75 70 5f 74 72 65 |eturn lo|okup_tre|
|00000720| 65 20 28 26 72 6f 6f 74 | 2c 20 6d 6f 64 6e 61 6d |e (&root|, modnam|
|00000730| 65 29 3b 0d 7d 0d 0d 73 | 74 61 74 69 63 20 4d 6f |e);.}..s|tatic Mo|
|00000740| 64 75 6c 65 0d 6c 6f 6f | 6b 75 70 5f 74 72 65 65 |dule.loo|kup_tree|
|00000750| 28 54 4e 4f 44 45 20 2a | 2a 72 6f 6f 74 70 74 72 |(TNODE *|*rootptr|
|00000760| 2c 20 63 68 61 72 20 2a | 6d 6f 64 6e 61 6d 65 29 |, char *|modname)|
|00000770| 20 7b 0d 20 20 20 20 20 | 69 66 20 28 2a 72 6f 6f | {.     |if (*roo|
|00000780| 74 70 74 72 3d 3d 4e 55 | 4c 4c 29 20 7b 0d 20 20 |tptr==NU|LL) {.  |
|00000790| 20 20 20 20 20 20 72 65 | 74 75 72 6e 20 4e 55 4c |      re|turn NUL|
|000007a0| 4c 3b 0d 20 20 20 20 20 | 7d 20 0d 20 20 20 20 20 |L;.     |} .     |
|000007b0| 69 66 20 28 73 74 72 63 | 6d 70 28 28 2a 72 6f 6f |if (strc|mp((*roo|
|000007c0| 74 70 74 72 29 2d 3e 64 | 61 74 61 2d 3e 6e 61 6d |tptr)->d|ata->nam|
|000007d0| 65 2c 6d 6f 64 6e 61 6d | 65 29 3d 3d 30 29 20 7b |e,modnam|e)==0) {|
|000007e0| 0d 20 20 20 20 20 20 20 | 20 20 72 65 74 75 72 6e |.       |  return|
|000007f0| 20 28 2a 72 6f 6f 74 70 | 74 72 29 2d 3e 64 61 74 | (*rootp|tr)->dat|
|00000800| 61 3b 0d 20 20 20 20 20 | 7d 20 65 6c 73 65 20 69 |a;.     |} else i|
|00000810| 66 20 28 73 74 72 63 6d | 70 28 28 2a 72 6f 6f 74 |f (strcm|p((*root|
|00000820| 70 74 72 29 2d 3e 64 61 | 74 61 2d 3e 6e 61 6d 65 |ptr)->da|ta->name|
|00000830| 2c 6d 6f 64 6e 61 6d 65 | 29 3c 30 29 20 7b 0d 20 |,modname|)<0) {. |
|00000840| 20 20 20 20 20 20 20 20 | 72 65 74 75 72 6e 20 6c |        |return l|
|00000850| 6f 6f 6b 75 70 5f 74 72 | 65 65 28 26 28 28 2a 72 |ookup_tr|ee(&((*r|
|00000860| 6f 6f 74 70 74 72 29 2d | 3e 6c 65 66 74 29 2c 6d |ootptr)-|>left),m|
|00000870| 6f 64 6e 61 6d 65 29 3b | 0d 20 20 20 20 20 7d 20 |odname);|.     } |
|00000880| 65 6c 73 65 20 2f 2a 20 | 3e 30 20 2a 2f 20 7b 0d |else /* |>0 */ {.|
|00000890| 20 20 20 20 20 20 20 20 | 20 72 65 74 75 72 6e 20 |        | return |
|000008a0| 6c 6f 6f 6b 75 70 5f 74 | 72 65 65 28 26 28 28 2a |lookup_t|ree(&((*|
|000008b0| 72 6f 6f 74 70 74 72 29 | 2d 3e 72 69 67 68 74 29 |rootptr)|->right)|
|000008c0| 2c 6d 6f 64 6e 61 6d 65 | 29 3b 0d 20 20 20 20 20 |,modname|);.     |
|000008d0| 7d 0d 7d 0d 40 20 25 64 | 65 66 20 6c 6f 6f 6b 75 |}.}.@ %d|ef looku|
|000008e0| 70 0d 0d 5b 5b 61 70 70 | 6c 79 5f 65 61 63 68 5f |p..[[app|ly_each_|
|000008f0| 6d 6f 64 75 6c 65 5d 5d | 20 74 61 6b 65 73 20 61 |module]]| takes a|
|00000900| 73 20 61 72 67 75 6d 65 | 6e 74 20 61 20 66 75 6e |s argume|nt a fun|
|00000910| 63 74 69 6f 6e 20 61 6e | 64 20 61 70 70 6c 69 65 |ction an|d applie|
|00000920| 73 0d 69 74 20 74 6f 20 | 65 61 63 68 20 6d 6f 64 |s.it to |each mod|
|00000930| 75 6c 65 20 69 6e 20 74 | 68 65 20 74 72 65 65 2e |ule in t|he tree.|
|00000940| 0d 54 68 69 73 20 6d 61 | 6b 65 73 20 69 74 20 65 |.This ma|kes it e|
|00000950| 61 73 79 20 74 6f 2c 20 | 66 6f 72 20 65 78 61 6d |asy to, |for exam|
|00000960| 70 6c 65 2c 20 72 65 6d | 6f 76 65 20 74 72 61 69 |ple, rem|ove trai|
|00000970| 6c 69 6e 67 20 6e 65 77 | 6c 69 6e 65 73 0d 66 72 |ling new|lines.fr|
|00000980| 6f 6d 20 65 61 63 68 20 | 6d 6f 64 75 6c 65 2e 0d |om each |module..|
|00000990| 3c 3c 2a 3e 3e 3d 0d 73 | 74 61 74 69 63 0d 76 6f |<<*>>=.s|tatic.vo|
|000009a0| 69 64 20 61 70 70 6c 79 | 5f 74 6f 5f 74 72 65 65 |id apply|_to_tree|
|000009b0| 28 54 4e 4f 44 45 20 2a | 70 2c 20 76 6f 69 64 20 |(TNODE *|p, void |
|000009c0| 28 2a 66 75 6e 29 28 4d | 6f 64 75 6c 65 29 29 20 |(*fun)(M|odule)) |
|000009d0| 7b 0d 20 20 20 20 69 66 | 20 28 70 20 21 3d 20 4e |{.    if| (p != N|
|000009e0| 55 4c 4c 29 20 7b 0d 20 | 20 20 20 20 20 20 20 61 |ULL) {. |       a|
|000009f0| 70 70 6c 79 5f 74 6f 5f | 74 72 65 65 28 70 2d 3e |pply_to_|tree(p->|
|00000a00| 6c 65 66 74 2c 66 75 6e | 29 3b 0d 20 20 20 20 20 |left,fun|);.     |
|00000a10| 20 20 20 28 2a 66 75 6e | 29 28 70 2d 3e 64 61 74 |   (*fun|)(p->dat|
|00000a20| 61 29 3b 0d 20 20 20 20 | 20 20 20 20 61 70 70 6c |a);.    |    appl|
|00000a30| 79 5f 74 6f 5f 74 72 65 | 65 28 70 2d 3e 72 69 67 |y_to_tre|e(p->rig|
|00000a40| 68 74 2c 66 75 6e 29 3b | 0d 20 20 20 20 7d 0d 7d |ht,fun);|.    }.}|
|00000a50| 0d 76 6f 69 64 20 61 70 | 70 6c 79 5f 65 61 63 68 |.void ap|ply_each|
|00000a60| 5f 6d 6f 64 75 6c 65 28 | 76 6f 69 64 20 28 2a 66 |_module(|void (*f|
|00000a70| 75 6e 29 28 4d 6f 64 75 | 6c 65 29 29 20 7b 0d 20 |un)(Modu|le)) {. |
|00000a80| 20 20 20 61 70 70 6c 79 | 5f 74 6f 5f 74 72 65 65 |   apply|_to_tree|
|00000a90| 28 72 6f 6f 74 2c 66 75 | 6e 29 3b 0d 7d 0d 40 20 |(root,fu|n);.}.@ |
|00000aa0| 25 64 65 66 20 61 70 70 | 6c 79 5f 65 61 63 68 5f |%def app|ly_each_|
|00000ab0| 6d 6f 64 75 6c 65 0d    |                         |module. |        |
+--------+-------------------------+-------------------------+--------+--------+